package ru.scalabook.algorithms.combinatorics

/** A tiny class that extends a list with four combinatorial operations:
  * ''combinations'', ''subsets'', ''permutations'', ''variations''.
  *
  * You can find all the ideas behind this code at blog-post:
  *
  * https://kostyukov.net/posts/combinatorial-algorithms-in-scala/
  *
  * How to use this class.
  *
  * import CombinatorialOps.*
  *
  * val v = List(1, 2, 3).xvariations(2)
  *
  * The following functions are available:
  *
  *   - xcombinations(n) -- generates n-combinations
  *   - xsubsets -- generates all subsets
  *   - xvariations(n) -- generates n-variations
  *   - xpermutations -- generates all permutations
  *
  * @see
  *   <a
  *   href="https://kostyukov.net/posts/combinatorial-algorithms-in-scala/">Kostyukov.net:
  *   Combinatorial Algorithms in Scala</a>
  */
object CombinatorialOps:

  extension [A](l: List[A])

    /** Generates the combinations of this list with given length 'n'. The order
      * doesn't matter.
      *
      * The total number of k-combinations on n-length set might be calculated
      * as follows:
      *
      * C_k,n = n!/k!(n - k)!
      *
      * Time - O(C_k,n) Space - O(C_k,n)
      */
    def xcombinations(n: Int): List[List[A]] =
      if n > l.size then Nil
      else
        l match
          case _ :: _ if n == 1 => l.map(List(_))
          case hd :: tl =>
            tl.xcombinations(n - 1).map(hd :: _) ::: tl.xcombinations(n)
          case _ => Nil

    /** Generates all the subsets of this list. The order doesn't matter.
      *
      * The total number of subsets might be obtained from variations formula:
      *
      * S_n = sum(i=1..n) {C_i,n} = 2 ** n Time - O(S_n) Space - O(S_n)
      */
    def xsubsets: List[List[A]] =
      (2 to l.size).foldLeft(l.xcombinations(1))((a, i) =>
        l.xcombinations(i) ::: a
      )

    /** Generates the variations of this list with given length 'n'. The order
      * does matter.
      *
      * The total number of variations might be calculated as follows:
      *
      * V_k,n = n!/(n - k)!
      *
      * Time - O(V_k,n) Space - O(V_k,n)
      */
    def xvariations(n: Int): List[List[A]] =
      def mixmany(x: A, ll: List[List[A]]): List[List[A]] =
        ll match
          case hd :: tl => foldone(x, hd) ::: mixmany(x, tl)
          case _        => Nil

      def foldone(x: A, ll: List[A]): List[List[A]] =
        (1 to ll.length).foldLeft(List(x :: ll))((a, i) =>
          mixone(i, x, ll) :: a
        )

      def mixone(i: Int, x: A, ll: List[A]): List[A] =
        ll.slice(0, i) ::: (x :: ll.slice(i, ll.length))

      if n > l.size then Nil
      else
        l match
          case _ :: _ if n == 1 => l.map(List(_))
          case hd :: tl =>
            mixmany(hd, tl.xvariations(n - 1)) ::: tl.xvariations(n)
          case _ => Nil
    end xvariations

    /** Generates all permutations of this list. The order does matter.
      *
      * The total number of permutations might be calculated as follows:
      *
      * P_n = V_n,n = n!
      *
      * Time - O(n!) Space - O(n!)
      */
    def xpermutations: List[List[A]] = xvariations(l.size)
  end extension
end CombinatorialOps
